package com.south.base.arithmetic;

import java.util.Arrays;

/**
 * @author Administrator
 * @date 2019/6/21 17:10
 */
public class Sudoku {
    private char[] nums = new char[]{'1', '2', '3', '4', '5', '6', '7', '8', '9'};

    /**
     * 通过已填充的空格来解决数独问题。
     *
     * @param board
     */
    public void solveSudoku(char[][] board) {
        int[][][] keys = new int[3][9][9];
        if (!isValidSudoku(board, keys)) {
            return;
        }
        solveSudoku(0, 0, board, keys);
        for (char[] c : board) {
            System.out.println(Arrays.toString(c));
        }
    }

    /**
     * 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     *
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        int[][][] keys = new int[3][9][9];
        return isValidSudoku(board, keys);
    }

    private boolean solveSudoku(int i, int j, char[][] board, int[][][] keys) {
        if (j >= board.length) {
            j = 0;
            i++;
        }
        if (i >= board.length) {
            return true;
        }
        char c = board[i][j];
        if (c != '.') {
            return solveSudoku(i, j + 1, board, keys);
        }
        for (char num : nums) {
            if (isValidSudoku(i, j, keys, num)) {
                board[i][j] = num;
                if (solveSudoku(i, j + 1, board, keys)) {
                    return true;
                }
                board[i][j] = '.';
                resumeKeys(i, j, keys, num);
            }
        }
        return false;
    }

    private boolean isValidSudoku(char[][] board, int[][][] keys) {
        for (int i = 0; i < board.length; i++) {
            char[] rows = board[i];
            for (int j = 0; j < rows.length; j++) {
                char c = rows[j];
                if (c == '.') {
                    continue;
                }
                if (!isValidSudoku(i, j, keys, c)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValidSudoku(int i, int j, int[][][] keys, char num) {
        int index = num - '1';
        if (keys[0][i][index] > 0 || keys[1][j][index] > 0 || keys[2][i / 3 + 3 * (j / 3)][index] > 0) {
            return false;
        }
        // 确保行里没有重复
        keys[0][i][index]++;
        // 确保列里没有重复
        keys[1][j][index]++;
        // 确保九格子内没有重复
        keys[2][i / 3 + 3 * (j / 3)][index]++;
        return true;
    }

    private void resumeKeys(int i, int j, int[][][] keys, char num) {
        int index = num - '1';
        keys[0][i][index]--;
        keys[1][j][index]--;
        keys[2][i / 3 + 3 * (j / 3)][index]--;
    }
}
